package com.itheima.leetcode.od.b.graph;

import com.itheima.datastructure.queue.LinkedListQueue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * <h3>二叉树的广度优先遍历</h3>
 * 有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请输出层次遍历的结果。
 * <p>
 * 输入描述
 * <p>
 * 二叉树后序和中序遍历结果
 * <p>
 * 输出描述
 * <p>
 * 二叉树层序遍历结果
 * <p>
 * 示例1
 * <p>
 * 输入
 * <p>
 * CBEFDA CBAEDF
 * <p>
 * 输出
 * <p>
 * ABDCEF
 */
public class BFSBinaryBuildTrees {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        String post = sc.next();
        String mid = sc.next();*/

        String input = "CBEFDA CBAEDF";
        char[][] arr = Arrays.stream(input.split(" "))
                .map(s -> s.toCharArray())
                .toArray(char[][]::new);
        char[] post = arr[0];
        char[] mid = arr[1];

        System.out.println(levelOrder(buildTree(mid, post)));
        System.out.println(BFSOrder(buildTree(mid, post)));
    }


    /**
     * 先通过后序遍历结果定位根节点
     * 再结合中序遍历结果切分左右子树
     *
     * @param inOrder
     * @param postOrder
     * @return
     */
    public static TreeNode buildTree(char[] inOrder, char[] postOrder) {
        if (inOrder.length == 0) {
            return null;
        }
        // 根
        char rootValue = postOrder[postOrder.length - 1];
        TreeNode root = new TreeNode(rootValue);
        // 切分左右子树
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
                char[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
                char[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);

                char[] postLeft = Arrays.copyOfRange(postOrder, 0, i);
                char[] postRight = Arrays.copyOfRange(postOrder, i, postOrder.length - 1);

                root.left = buildTree(inLeft, postLeft);
                root.right = buildTree(inRight, postRight);
                break;
            }
        }
        return root;
    }

    /**
     * 层序遍历
     *
     * @param root
     * @return
     */
    public static List<List<String>> levelOrder(TreeNode root) {
        List<List<String>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
        queue.offer(root);
        while (!queue.isEmpty()) {

            List<String> level = new ArrayList<>(); // 保存每一层结果
            LinkedListQueue<TreeNode> temQueue = new LinkedListQueue<>();
            while (!queue.isEmpty()) {
                TreeNode n = queue.poll();
                level.add(String.valueOf(n.val));
                if (n.left != null) {
                    temQueue.offer(n.left);
                }
                if (n.right != null) {
                    temQueue.offer(n.right);
                }
            }
            result.add(level);
            queue = temQueue;
        }

        return result;
    }

    /**
     * 广度遍历
     *
     * @param root
     * @return
     */
    public static String BFSOrder(TreeNode root) {
        if (root == null) {
            return "";
        }

        LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
        queue.offer(root);
        List<String> level = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode n = queue.poll();
            level.add(String.valueOf(n.val));
            if (n.left != null) {
                queue.offer(n.left);
            }
            if (n.right != null) {
                queue.offer(n.right);
            }
        }

        return level.stream().collect(Collectors.joining(""));
    }
}